package BinaryTree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

//二叉树的锯齿形层序遍历: https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
//时间复杂度: O(n)
public class Code3 {
    public static int MAXN=2001;
    public static TreeNode[] queue=new TreeNode[MAXN];
    public static int l,r;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans=new ArrayList<>();
        boolean flag=true;
        if(root!=null) {
            l=r=0;
            queue[r++]=root;
            while(l<r) {
                int size=r-l;
                List<Integer> list=new ArrayList<Integer>();
                for(int i=0;i<size;i++) {
                    TreeNode cur=queue[l++];
                    if(flag==true) {
                        list.add(cur.val);
                    }
                    else {
                        list.add(0,cur.val);
                    }
                    if(cur.left!=null) {
                        queue[r++]=cur.left;;
                    }
                    if(cur.right!=null) {
                        queue[r++]=cur.right;
                    }
                }
                flag=!flag;
                ans.add(list);
            }
        }
        return ans;
    }
}
